package StringAlgorithm;

public class leet_5 {
    public static void main(String[] args) {
        Solution_5 p =new Solution_5();

        String s = "bb";
        String result = p.longestPalindrome(s);
        System.out.println(result);

    }
}

class Solution_5 {
    public String longestPalindrome(String s) {
        String value = longestCenter(s);
        return value;
    }

    /**
     * 中心扩散方法
     * 1.由于回文串长度存在奇偶数的问题，其中奇数的中心就是中间点 但是偶数的中心是2个数
     * 2.所以遍历每个位置，其中计算奇偶2个可能性的值，所以 len-1 这个下标就不需要考虑
     * 3.中心的扩展问题，如果中心的位置在向二边扩展中一旦发现2边不相同时，就不需要进行扩展了。
     *   这是由于回文的特征来的，回文的子串必定回文，所以当发现不属于回文时就可以终结数据了
     * @param s
     * @return
     */
    public String longestCenter(String s){
        int len = s.length();
        if(len<2){
            return s;
        }

        char[] charS = s.toCharArray();
        int beginIndex = 0;
        int maxLength = 1;
        for(int i=0; i<len-1; i++){
            // 只需要到倒数第二个就好，因为最后一个无法往右进行扩散 所以无意义
            int len_1 = isPalindromicCenter(charS, i, i);
            int len_2 = isPalindromicCenter(charS, i, i+1);
            int tmpLen = Math.max(len_1, len_2);
            if(tmpLen > maxLength){
                beginIndex = i-(tmpLen-1)/2;
                maxLength = tmpLen;
            }

        }
        return s.substring(beginIndex, beginIndex+maxLength);
    }


    /**
     * 中心扩散的回文字符串的判断
     *
     * @param charS
     * @param centerOne  中心位置一
     * @param centerTwo  中心位置二
     * @return 最大长度
     */
    public int isPalindromicCenter(char[] charS, int centerOne, int centerTwo){
        while(centerOne>=0 && centerTwo<=charS.length-1){
            if(charS[centerOne]!=charS[centerTwo]){
                break;
            }
            centerOne--;
            centerTwo++;
        }
        int len = centerTwo-centerOne-1;
        return len;
    }



    /**
     * 暴力法
     * 每一个位置都往后遍历寻找最大的串
     * @param s
     * @return
     */
    public String longestViolence(String s){
        // 长度
        int len = s.length();
        if(len<2){
            return s;
        }
        // 定期长度与起始点与字符串数组
        char[] sChar = s.toCharArray();
        int beginIndex = 0;
        int maxLen = 1;
        for(int i=0; i<len; i++){
            for(int j=i+1; j<len; j++){
                // 每一个位置与后面所有的字符串组合，查看是否为回文字符串
                if((j-i+1)>maxLen){
                    // 是不是超过当前最大的回文串否则不比较
                    boolean isValue = isPalindromicViolence(sChar, i, j);
                    if(isValue){
                        // 是不是回文串
                        beginIndex = i;
                        maxLen = j-i+1;
                    }
                }
            }
        }
        return s.substring(beginIndex, beginIndex+maxLen);
    }

    /**
     * 暴力解法的回文判断
     * @param chars
     * @param begin
     * @param end
     * @return
     */
    public boolean isPalindromicViolence(char[] chars, int begin, int end){
        while(begin<end){
            // 查看是不是相同
            if(chars[begin] != chars[end]){
                return false;
            }
            begin++;
            end--;
        }
        return true;
    }


}

